package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Factorization {

    /**
     * 欧几里得算法求最大公约数
     * @param m 第一个数
     * @param n 第二个数
     * @return 最大公约数
     */
    public static long gcd(long m, long n) {
        if (m < n) {
            long temp = m;
            m = n;
            n = temp;
        }
        while (m % n != 0) {
            long temp = m;
            m = n;
            n = temp % n;
        }
        return n;
    }

    /**
     * 线性筛（欧拉筛）生成小于等于n的素数列表
     * @param n 上限
     * @return 素数列表
     */
    public static List<Long> sieve(int n) {
        int[] mpfs = new int[n + 1]; // 存储最小质因子
        List<Long> pn = new ArrayList<>(); // 存储素数

        for (int i = 2; i <= n; i++) {
            int mpf = mpfs[i];
            if (mpf == 0) {
                pn.add((long) i);
                mpf = i;
            }
            for (long p : pn) {
                int pInt = (int) p;
                if (pInt > mpf) {
                    break;
                }
                long x = p * i;
                if (x > n) {
                    break;
                }
                mpfs[(int) x] = pInt;
            }
        }
        return pn;
    }

    /**
     * Pollard Rho算法尝试分解n
     * @param n 待分解的数
     * @return 分解结果数组 [p, q]，若无法分解则为 [1, n]
     */
    public static long[] pollard(long n) {
        Random random = new Random();
        long b = 100000; // 初始值 10_0000
        while (b <= 1000000) { // 上限 100_0000
            long a = random.nextLong(n - 2) + 2; // 生成2到n-1的随机数
            long g = gcd(a, n);
            if (g > 1) {
                return new long[]{g, n / g};
            }

            List<Long> primes = sieve((int) b);
            for (long p : primes) {
                if (p >= b) {
                    continue;
                }

                long pPower = 1;
                while (pPower * p <= b) {
                    pPower *= p;
                }
                g = gcd(pPower - 1, n);
                if (g > 1 && g < n) {
                    return new long[]{g, n / g};
                }
            }
            b <<= 1; // b *= 2
        }
        return new long[]{1, n};
    }

    /**
     * 递归分解n的所有质因子
     * @param n 待分解的数
     * @return 质因子列表（升序）
     */
    public static List<Long> factor(long n) {
        List<Long> factors = new ArrayList<>();
        List<Long> stack = new ArrayList<>();
        stack.add(n);

        while (!stack.isEmpty()) {
            long x = stack.remove(stack.size() - 1); // 模拟pop()
            if (x == 2) {
                factors.add(0, x); // 插入到列表头部
                continue;
            }

            long[] pq;
            if ((x & 1) == 1) { // 奇数
                pq = pollard(x);
            } else { // 偶数，分解出2
                pq = new long[]{2, x >> 1};
            }

            long p = pq[0];
            long q = pq[1];
            if (p == 1) {
                factors.add(0, q);
            } else {
                stack.add(p);
                stack.add(q);
            }
        }
        return factors;
    }

    public static void main(String[] args) {
        long number = 200;
        List<Long> factors = factor(number);
        System.out.println(factors); // 输出 [2, 2, 2, 5, 5]
    }
}